package com.ifreeee.sort.radixsort;

import com.ifreeee.sort.quicksort.QuickSort;
import com.ifreeee.utils.RandomUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * 基数排序，存在问题
 */

public class RadixSort {

    private static int baseNum = 1000;//基数
    List<ArrayList<Integer>> bks;//桶，一定要使用性能强劲的可变数组替代, 为了节省空间，也为了提高性能

    public RadixSort()
    {
        bks = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < baseNum; i += 1) {
            bks.add(new ArrayList<Integer>());
        }
    }

    /*public RadixSort(int baseNum){
        bks = new ArrayList<ArrayList<Integer>>();
        this.baseNum = baseNum > 2 ? baseNum : 2;
        for(int i = 0; i < baseNum; i += 1){
            bks.add(new ArrayList<Integer>());
        }
    }*/

    /**
     * 基数排序（仅限于正数 Positive number）
     *
     * @param arr
     */
    public static void radixSortPositive(int[] arr)
    {
        //初始化
        int len = arr.length;//数组长度
        int arrIdx = 0;//初始化变量，记录放回到原数组的哪一个下标了
        int[][] bks = new int[baseNum][len];//baseNum个桶
        int[] bksLen = new int[baseNum];//记录每个桶的有效元素
        int maxL = getMaxDigit(arr, baseNum);//1. 获取最高位数
        int temp;
        int i, j, k, m;
        //排序操作
        for (i = 0, m = 1; i < maxL; i += 1, m *= baseNum) {//最高位数为多少就遍历多少次
            for (j = 0; j < len; j += 1) {//遍历数组，将数据从原数组取出按照规则放入桶
                //将数据从原数组取出按照规则放入桶
                temp = arr[j] / m % baseNum;
                bks[temp][bksLen[temp]] = arr[j];
                bksLen[temp] += 1;
            }
            arrIdx = 0;
            //遍历每个桶，将每个数按顺序拿出来 放回原数组
            for (j = 0; j < baseNum; j += 1) {//遍历每一个桶
                for (k = 0, temp = bksLen[j]; k < temp; k += 1) {//取出每一个数放回原数组
                    arr[arrIdx] = bks[j][k];
                    arrIdx += 1;
                }
                bksLen[j] = 0;//然后把这个桶清掉
            }
        }
    }

    /**
     * 基数排序（仅限于负数）
     *
     * @param arr
     */
    public static void radixSortNegative(int[] arr)
    {
        int len = arr.length;//数组长度
        int arrIdx = 0;//初始化变量，记录放回到原数组的哪一个下标了
        int[][] bks = new int[baseNum][len];//baseNum个桶
        int[] bksLen = new int[baseNum];//记录每个桶的有效元素
        int maxL = getMaxDigit(arr, baseNum);//1. 获取最高位数
        int temp;
        int i, j, k, m;
        //排序操作
        for (i = 0, m = 1; i < maxL; i += 1, m *= baseNum) {//最高位数为多少就遍历多少次
            for (j = 0; j < len; j += 1) {//遍历数组，将数据从原数组取出按照规则放入桶
                //将数据从原数组取出按照规则放入桶
                temp = -arr[j] / m % baseNum;
                bks[temp][bksLen[temp]] = arr[j];
                bksLen[temp] += 1;
            }
            arrIdx = 0;
            //遍历每个桶，将每个数按顺序拿出来 放回原数组
            for (j = baseNum - 1; j > -1; j -= 1) {//遍历每一个桶
                for (k = 0, temp = bksLen[j]; k < temp; k += 1) {//取出每一个数放回原数组
                    arr[arrIdx] = bks[j][k];
                    arrIdx += 1;
                }
                bksLen[j] = 0;//然后把这个桶清掉
            }
        }
    }

    /**
     * 基数排序（兼容正负数，还有改进的方法，但也是空间换时间）
     *
     * @param arr
     */
    public static void radixSort(int[] arr)
    {
        int i, len, arrIdx;
        int m = 0, n = 0;
        for (i = 0, len = arr.length; i < len; i += 1) {
            if (arr[i] < 0) {
                m += 1;
            }
        }
        int[] negativeArr = new int[m];
        int[] positiveArr = new int[len - m];
        for (i = 0, len = arr.length, m = 0, n = 0; i < len; i += 1) {
            if (arr[i] < 0) {
                negativeArr[m] = arr[i];
                m += 1;
            } else {
                positiveArr[n] = arr[i];
                n += 1;
            }
        }
        RadixSort.radixSortNegative(negativeArr);
        RadixSort.radixSortPositive(positiveArr);
        for (i = 0, len = negativeArr.length; i < len; i += 1) {
            arr[i] = negativeArr[i];
        }
        for (i = 0, arrIdx = len, len = positiveArr.length; i < len; i += 1) {
            arr[arrIdx] = positiveArr[i];
            arrIdx += 1;
        }
    }

    /**
     * 获取数组里 所有数的位数 最大位数 是多少（兼容正负数）
     *
     * @param arr 传入一个数组
     * @return 返回数组的最高位数
     */
    public static int getMaxDigit(int[] arr, int basenum)
    {
        int maxL = getNumLenght(getMaxValue(arr), basenum);//找到最大的数
        int minL = getNumLenght(getMinValue(arr), basenum);//找到最小的数（负数也可能是最高位）
        return maxL > minL ? maxL : minL;//比较两个位数，返回大的位数
    }

    /**
     * 返回最大数
     *
     * @param arr 传入一个数组
     * @return 最大值
     */
    public static int getMaxValue(int[] arr)
    {
        int maxNum = arr[0];//记录最大值
        for (int value : arr) {//找最大值
            if (value > maxNum) {
                maxNum = value;
            }
        }
        return maxNum;
    }

    /**
     * 返回最小数
     *
     * @param arr 传入一个数组
     * @return 最小值
     */
    public static int getMinValue(int[] arr)
    {
        int minNum = arr[0];//记录最小值
        for (int value : arr) {//找最小值
            if (value < minNum) {
                minNum = value;
            }
        }
        return minNum;
    }

    /**
     * 获取一个数的 位数
     *
     * @param num     数
     * @param basenum 进制数
     * @return
     */
    public static int getNumLenght(int num, int basenum)
    {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;//记录位数
        for (int temp = num; temp != 0; temp /= basenum) {//计算位数
            lenght += 1;
        }
        return lenght;//返回位数
    }

    /**
     * 基数排序（链表的方式改进）
     *
     * @param arr
     */
    public static void radixSortByLinked(int[] arr)
    {
        System.out.println(System.currentTimeMillis());
        //初始化
        int len = arr.length;//数组长度
        int arrIdx = 0;//初始化变量，记录放回到原数组的哪一个下标了
        int maxL = getMaxDigit(arr, baseNum);//1. 获取最高位数
        int te, mp;
        int i, j, m, n;
        //base基数 (baseNum * 2 - 1)个桶（由链表实现） ,
        int bksNum = baseNum * 2 - 1;
        int bkTemp = baseNum - 1;//位数n 放到 n + baseNum - 1 个桶 = n + bkTemp
        LinkedNum[] bksHead = new LinkedNum[bksNum];
        LinkedNum[] bksTemp = new LinkedNum[bksNum];
        LinkedNum[] bksEnd = new LinkedNum[bksNum];
        LinkedNum arrTemp = new LinkedNum();
        LinkedNum tete = null, mpmp = null;
        for (i = 0; i < bksNum; i++) {
            bksHead[i] = new LinkedNum();
            bksTemp[i] = bksHead[i];
            bksEnd[i] = bksHead[i];
        }
        System.out.println(System.currentTimeMillis());
        //排序操作
        n = maxL - 1;
        for (i = 0, m = 1; i < maxL; i += 1, m *= baseNum) {//最高位数为多少就遍历多少次
            System.out.println(i + "\t1\t" + System.currentTimeMillis());
            if (i == 0) {//第一次从arr将数据放入桶
                for (j = 0; j < len; j++) {
                    te = arr[j];
                    mp = te / m % baseNum + bkTemp;
                    LinkedNum ln = new LinkedNum();
                    ln.num = te;
                    bksEnd[mp] = ln;
                    bksTemp[mp].next = ln;
                    bksTemp[mp] = ln;
                }
            } else {//不是第一次，从arrTemp，将数据放入桶
                mpmp = arrTemp.next;
                while (mpmp != null) {
                    mp = mpmp.num / m % baseNum + bkTemp;//根据数值判断应该放到哪个桶
                    //放到桶
                    bksEnd[mp] = mpmp;
                    bksTemp[mp].next = mpmp;
                    bksTemp[mp] = mpmp;
                    mpmp = mpmp.next;//后移
                }
            }
            System.out.println(i + "\t2\t" + System.currentTimeMillis());
            if (n == i) {//最后一次，从桶将数据拿回arr
                for (j = 0; j < bksNum; j++) {//遍历每一个桶
                    bksEnd[j].next = null;//断掉尾巴
                    tete = bksHead[j].next;//每个桶的第一个数
                    while (tete != null) {//遍历完则退出
                        arr[arrIdx++] = tete.num;//将数放入数组
                        tete = tete.next;//后移
                    }
                }
            } else {//不是最后一次，从桶将数据拿回arrTemp
                tete = arrTemp;//tete代表尾部
                for (j = 0; j < bksNum; j++) {
                    mpmp = bksHead[j].next;//获取当前桶的头部
                    if (bksHead[j] == bksEnd[j]) continue;//桶为空
                    tete.next = mpmp;
                    tete = bksEnd[j];
                    bksTemp[j] = bksHead[j];//将辅助指针复原，表示桶清空
                    bksEnd[j] = bksHead[j];
                }
                tete.next = null;
            }
            System.out.println(i + "\t3\t" + System.currentTimeMillis());
        }
    }

    /**
     * 基数排序（链表的方式改进）
     *
     * @param arr
     */
    public static void radixSortByLinked1(int[] arr)
    {
        System.out.println(System.currentTimeMillis());
        //初始化
        int len = arr.length;//数组长度
        int arrIdx = 0;//初始化变量，记录放回到原数组的哪一个下标了
        int maxL = getMaxDigit(arr, baseNum);//1. 获取最高位数
        int te, mp;
        int i, j, m, n;
        //base基数 (baseNum * 2 - 1)个桶（由链表实现） ,
        int bksNum = baseNum * 2 - 1;
        int bkTemp = baseNum - 1;//位数n 放到 n + baseNum - 1 个桶 = n + bkTemp
        LinkedNum[] bksHead = new LinkedNum[bksNum];
        LinkedNum[] bksEnd = new LinkedNum[bksNum];
        LinkedNum arrTemp = new LinkedNum();
        LinkedNum tete = null, mpmp = null;
        for (i = 0; i < bksNum; i++) {
            bksHead[i] = new LinkedNum();
            bksEnd[i] = bksHead[i];
        }
        System.out.println(System.currentTimeMillis());
        //排序操作
        n = maxL - 1;
        for (i = 0, m = 1; i < maxL; i += 1, m *= baseNum) {//最高位数为多少就遍历多少次
            System.out.println(i + "\t1\t" + System.currentTimeMillis());
            if (i == 0) {//第一次从arr将数据放入桶
                for (j = 0; j < len; j++) {
                    te = arr[j];
                    mp = te / m % baseNum + bkTemp;
                    LinkedNum ln = new LinkedNum();
                    ln.num = te;
                    bksEnd[mp].next = ln;
                    bksEnd[mp] = ln;
                }
            } else {//不是第一次，从arrTemp，将数据放入桶
                mpmp = arrTemp.next;
                while (mpmp != null) {
                    mp = mpmp.num / m % baseNum + bkTemp;//根据数值判断应该放到哪个桶
                    //放到桶
                    bksEnd[mp].next = mpmp;
                    bksEnd[mp] = mpmp;
                    mpmp = mpmp.next;//后移
                }
            }
            System.out.println(i + "\t2\t" + System.currentTimeMillis());
            if (n == i) {//最后一次，从桶将数据拿回arr
                for (j = 0; j < bksNum; j++) {//遍历每一个桶
                    bksEnd[j].next = null;//断掉尾巴
                    tete = bksHead[j].next;//每个桶的第一个数
                    while (tete != null) {//遍历完则退出
                        arr[arrIdx++] = tete.num;//将数放入数组
                        tete = tete.next;//后移
                    }
                }
            } else {//不是最后一次，从桶将数据拿回arrTemp
                tete = arrTemp;//tete代表尾部
                for (j = 0; j < bksNum; j++) {
                    mpmp = bksHead[j].next;//获取当前桶的头部
                    if (bksHead[j] == bksEnd[j]) continue;//桶为空
                    tete.next = mpmp;
                    tete = bksEnd[j];
                    bksEnd[j] = bksHead[j];
                }
                tete.next = null;
            }
            System.out.println(i + "\t3\t" + System.currentTimeMillis());
        }
    }

    @Test
    public void test2()
    {
        int i = 0, j = 0, k = 0;
        int len = 10000000;
        Random r = new Random();
        int[] arr1 = new int[len];
        int[] arr2 = new int[len];
        int[] arr3 = new int[len];
        LinkedNum head1 = new LinkedNum();
        LinkedNum head2 = new LinkedNum();
        LinkedNum end1 = head1;
        LinkedNum temp = null;
        for(i = 0; i < len; i++){
            arr1[i] = RandomUtils.randomNum(-len, len, r);
        }
        //数组 与 链表 的遍历速度对比
        long l1 = System.currentTimeMillis();
        //数组 arr1 到数组 arr2
        for(i = 0; i < len; i++){
            arr2[i] = arr1[i];
        }
        long l2 = System.currentTimeMillis();
        //数组 arr2 到链表 head1
        for(i = 0; i < len; i++){
            LinkedNum ln = new LinkedNum();
            ln.num = arr2[i];
            end1.next = ln;
            end1 = ln;
        }
        end1 = head2;
        long l3 = System.currentTimeMillis();
        //链表 head1 到 链表 head2
        temp = head1.next;
        while(temp !=  null){
            end1.next = temp;
            end1 = temp;
            temp = temp.next;
        }
        long l4 = System.currentTimeMillis();
        //链表 head2 到 数组 arr3
        temp = head2.next;
        i = 0;
        while(temp !=  null){
            arr3[i++] = temp.num;
            temp = temp.next;
        }
        long l5 = System.currentTimeMillis();
        //此时arr1 arr2 head1 head2 arr3 都有值
        for(int value :arr3){//保证arr3不被虚拟机优化
            i += value;
        }
        System.out.println((l2 - l1) + "ms\n" + (l3 - l2) + "ms\n"  + (l4 - l3) + "ms\n"  + (l5 - l4) + "ms\n" + i);
    }

    /**
     * 基数排序测试
     */
    @Test
    public void test1()
    {
        Random r = new Random();//随机数对象
        int num1 = 0;//代码一的时间
        int num2 = 0;//代码二的时间
        int num3 = 0;//代码三的时间
        int len = 10000000;//测试的数据量
        int time = 1;
        for (int j = 0; j < time; j += 1) {
            //初始化操作
            int[] arr = new int[len];
            int[] arr1 = new int[len];
            int[] arr2 = new int[len];
            for (int i = 0; i < len; i += 1) {
                int a = RandomUtils.randomNum(-len, len, r);
//                int a = r.nextInt(len);
                arr[i] = a;//
                arr1[i] = a;//
                arr2[i] = a;//三个数组数据相同
            }
            //希尔排序无需初始化准备
            long t1 = System.currentTimeMillis();
            //代码一
            QuickSort.quickSort(arr);
            long t2 = System.currentTimeMillis();
            //代码二
            RadixSort.radixSort/*ByLinked1*/(arr1);
            long t3 = System.currentTimeMillis();
            //代码三
            Arrays.sort(arr2);
            long t4 = System.currentTimeMillis();
            num1 += (t2 - t1);
            num2 += (t3 - t2);
            num3 += (t4 - t3);
            for (int i = 0; i < len; i += 1) {
                if (arr[i] != arr1[i] || arr[i] != arr2[i]) {
                    System.out.println("错误");
                }
            }
//            System.out.println(Arrays.toString(arr));
//            System.out.println(Arrays.toString(arr1));
//            System.out.println(Arrays.toString(arr2));
        }

        System.out.println("数据量：" + len + "\n测试次数：" + time);
        System.out.println("快速排序 耗时：" + num1 + "\n基数排序 耗时：" + num2 + "\nTimSort排序 耗时：" + num3);
        /*
            数据量：100000
            测试次数：300
            快速排序 耗时：2731
            基数排序 耗时：976
            TimSort排序 耗时：1681

            数据量：1000000
            测试次数：100
            快速排序 耗时：10494
            基数排序 耗时：3424
            TimSort排序 耗时：6517

            数据量：50000000
            测试次数：1
            快速排序 耗时：6904
            基数排序 耗时：2953
            TimSort排序 耗时：4296

            数据量：100000000
            测试次数：1
            快速排序 耗时：14293
            基数排序 耗时：5843
            TimSort排序 耗时：9029

            结论：基数排序最快
            改进：已改进
            下一个优化方案：增大基数，由链表实现可变长度队列，由于链表
        */
    }
}
